/* 
  归并排序，
  使用分治的思想拆分数组为更小的数组进行排序，然后在合并左右两个数组
 */

var sortUtil = {
  sort(arr) {
    this._sort(arr, 0, arr.length - 1);
  },
  _sort(arr, l, r) {
    // 2 当数组长度小的时候，可以使用选择排序，提高效果
   /*  if (r - l <= 15) {
      insertArr(arr, l, r);
      return;
    } */
    if (l >= r) {
      return;
    }
    const mid = Math.floor(l + (r - l) / 2);
    console.log(mid);

    this._sort(arr, l, mid);
    this._sort(arr, mid + 1, r);
    // 1 优化，如果左右两边已经是排好序的话，那么就不用merge
    if (arr[mid] > arr[mid + 1]) {
      this.merge(arr, l, mid, r);
    }
  },
  merge(arr, l, mid, r) {
    const temp = arr.slice(l, r + 1);
    let i = l;
    let j = mid + 1;
    for (let k = l; k <= r; k++) {
      if (i > mid) {
        arr[k] = temp[j - l];
        j++;
      } else if (j > r) {
        arr[k] = temp[i - l];
        i++;
      } else if (temp[i - l] < temp[j - l]) {
        arr[k] = temp[i - l];
        i++;
      } else {
        arr[k] = temp[j - l];
        j++;
      }
    }
  },
};

var a = [3, 2, 4, 7, 21, 3, 4, 6, 87];
sortUtil.sort(a);
console.log(a);
